package org.example.myleet.p438;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (p.length() > s.length()) {
            return result;
        }
        int[] pCharCount = new int[26];
        for (char c : p.toCharArray()) {
            ++pCharCount[c - 'a'];
        }
        int[] windowCharCount = new int[26];
        for (int i = 0; i < p.length(); ++i) {
            ++windowCharCount[s.charAt(i) - 'a'];
        }
        for (int i = 0; i <= s.length() - p.length(); ++i) {
            boolean found = true;
            for (int j = 0; j < 26; ++j) {
                if (pCharCount[j] != windowCharCount[j]) {
                    found = false;
                    break;
                }
            }
            if (found) {
                result.add(i);
            }
            if (i + p.length() < s.length()) {
                --windowCharCount[s.charAt(i) - 'a'];
                ++windowCharCount[s.charAt(i + p.length()) - 'a'];
            }
        }
        return result;
    }
}
